import java.util.*;


public class Solution {
    public void heapSort(int[] arr) {
        // 构造大顶堆，从第一个非叶子结点开始
        for (int i = (arr.length >> 1) - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        for (int i = arr.length - 1; i > 0; i--) { // 注意这里是大于0
            // 堆顶元素和末尾元素交换
            swap(arr, 0, i);
            // 重新调整堆
            adjustHeap(arr, 0, i);
        }
    }

    /**
     * 调节大顶堆，这个过程只是调整，建立在创建好的基础上
     *
     * @param arr    堆数组
     * @param i      开始调节的结点，即调节该结点为根结点的子树
     * @param length 构成堆的数字个数
     */
    private void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        // 从i的左子节点开始
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
            // 如果右子节点比左子节点大的话，就把k指向右子节点
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            // 如果小于子节点，就把子节点赋值给当前结点
            if (temp < arr[k]) { // 注意此处是temp，不是arr[i]
                arr[i] = arr[k];
                // i指向子节点，开始调整子节点
                i = k;
            } else {
                break;
            }
        }
        // 将temp放在最终位置
        arr[i] = temp;
    }

    private void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 14, 5, 2, 7, 6, 8, 3, 9};
        new Solution().heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
